// 1stMissingPositive.cpp : Defines the entry point for the console application.
//
/*
 Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space. 
*/

#include "stdafx.h"
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n == 0) return 1;
    
        for(int i = 0; i< n; i++)
        {
            if(A[i] <1 || A[i] >n)
            {
                A[i] = 0;
				continue;
            }
            if(A[i] == i+1)
                continue;
            else
            {
                int nTemp = A[A[i]-1];
                A[A[i]-1] = A[i];
                
                while(nTemp>=1 && nTemp <=n)
                {
                    
                    int nTemp2 = A[nTemp -1];
					if(nTemp2 == nTemp)
						break;
                    A[nTemp-1] = nTemp;
                    nTemp = nTemp2;
                    
                }
                
                
            }

        }

        int i =0;
        for(; i<n; i++)
        {
            if(i+1 !=A[i])
                break;
        }
        return i+1;
        
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
	Solution S;
	int test[2] ={1, 1};
	S.firstMissingPositive(test, 2);
	return 0;
}

